package com.LeeCode;

import java.util.Arrays;

/**
 * 和有限的最长子序列
 */

public class Code2389 {
    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 1};
        int[] queries = {3, 10, 21};
        System.out.println(Arrays.toString(new Code2389().answerQueries(nums, queries)));
    }

    public int[] answerQueries(int[] nums, int[] queries) {
        int[] ans = new int[queries.length];
        Arrays.sort(nums);
        int[] preSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        for (int i = 0; i < queries.length; i++) {
            int index = lowerBound(preSum, queries[i]);
            if (index == preSum.length || preSum[index] > queries[i])
                ans[i] = index - 1;
            else
                ans[i] = index;
        }

        return ans;
    }

    private int lowerBound(int[] nums, int target) {
        int left = -1, right = nums.length, mid;
        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
